#include <stdio.h>
// 【二分查找】
/**
 * @brief 二分查找函数，时间复杂度O(log n)
 * @param arr 排序数组
 * @param n 数组长度
 * @param target 目标值
 * @return 目标值的索引，未找到返回-1
 */
int BinarySearch(int arr[], int n, int target)
{
  int low = 0, high = n - 1;
  while (low <= high)
  {
    int mid = low + (high - low) / 2;
    if (arr[mid] == target)
    {
      return mid;
    }
    else if (arr[mid] < target)
    {
      low = mid + 1;
    }
    else
    {
      high = mid - 1;
    }
  }
  return -1;
}

int main()
{
  int n, target;
  // 输入数组长度
  printf("Enter the size of the array: ");
  scanf("%d", &n);
  int arr[n];
  // 输入数组元素
  for (int i = 0; i < n; i++)
  {
    printf("Enter element %d: ", i + 1);
    scanf("%d", &arr[i]);
  }
  // 输入目标值
  printf("Enter the target value: ");
  scanf("%d", &target);

  int index = BinarySearch(arr, n, target);

  if (index != -1)
  {
    printf("%d", index);
  }
  else
  {
    printf("Not Found");
  }

  return 0;
}